/*
a通过多少次变换使得a变成b
如果a[i]=b[j],不需要修改，dp[i+1][j+1]=dp[i][j]->dp[i][j]=dp[i-1][j-1]
如果a[i]!=b[j],需要修改
  1）将a[i]修改成b[i]，dp[i+1][j+1]=dp[i-1][j-1]+1 
    当a[i-1]!=b[j-1]的时候-> dp[i][j]=dp[i-1][j-1]+1
  2)删除操作，直接将a[i]删除，dp[i][j+1]（因为a[i]被删除，但下一个字符到了a[i]的位置，对应的比较位置到了b[j+1]
    dp[i][j+1]=dp[i][j]+1 
    当a[i-1]!=b[j-1]的时候 dp[i][j]可能通dp[i-1][j]转换而来
  3)插入操作，在a[i]后添加一个b[j],那么此时a[i+1]和b[j]对应，dp[i+1][j]=dp[i][j]+1
    当a[i-1]!=b[j-1]的时候 dp[i][j]可能通过dp[i][j-1]转移而来
*/
#include<bits/stdc++.h>
using namespace std;

const int N = 1e3+5;
char s[N], t[N];
int dp[N][N];// 前i个和包括了前j个要改几次 
int main() {
  scanf("%s %s", s + 1, t + 1);
  int n = strlen(s+1), m = strlen(t+1);
  memset(dp, 0x3f, sizeof dp);
  
  dp[0][0] = 0;
  
  for(int i = 1; i <= n; ++i) {
    dp[i][0] = 0;
    for(int j = 1; j <= m && j <= i; ++j) {
      if(s[i] == t[j]) {
        dp[i][j] = dp[i-1][j-1];
      } else {
          dp[i][j] = min(dp[i-1][j], dp[i-1][j-1] + 1);
      }
    }
  }
  cout << dp[n][m] << endl;
}
